The present invention relates generally to cryptographic methods and systems to be used in digital data processing, and in particular, is directed to methods and systems for constructing large substitution boxes for use in improving the security of symmetric block ciphers.
There are two general types of key-based cryptographic algorithms: asymmetric, also known as public-key, and symmetric. Public-key algorithms are designed so that the key used to decrypt the message is different from that used to encrypt the message. The encryption keys may be made public because the decryption key cannot be calculated from the encryption key. By contrast, in symmetric algorithms, the encryption key and decryption keys are either the same or may be calculated from one another.
There are two types of symmetric algorithms: stream ciphers and block ciphers. Stream ciphers operate on data one bit at a time while block ciphers operate on blocks of data where each block can be as large as 64 bits or more. The U.S. government standard Data Encryption Standard (DES) is one example of a symmetric block algorithm that encrypts using 64-bit blocks.
The security of a cryptosystem depends on its ability to mask the unavoidable redundancies in the underlying plaintext to make it impossible or computationally infeasible for an interloper to recreate it from the ciphertext. Confusion and diffusion are two general methods of obscuring redundancies. Good block ciphers will perform a number of bit-for-bit substitutions to introduce confusion. Diffusion is obtained by transposing, or rearranging the order of, the bits of the plaintext or ciphertext. Block ciphers typically employ successive iterations of both confusion and diffusion. Each iteration, or "round," contains both substitution and permutation.
Many block ciphers are based on Feistel networks because the underlying mathematical principles of Feistel networks guarantee that the cipher will be invertible. Both DES and the Northern Telecom-developed cipher, CAST, are examples of Feistel network-based ciphers.
FIGS. 1 and 2 are flow diagrams of the DES enciphering process. As shown in FIG. 1, DES is a typical Feistel network. To start, the algorithm takes a block of 64 bits and, after a permutation, divides the block into two equal-length halves. The cipher then performs a set of iterations where the output of the ith round is determined from the output of the previous round. In particular, EQU L.sub.i =R.sub.i-1 EQU R.sub.i =L.sub.i-1 .sym..function.(R.sub.i-1,K.sub.i-1)
In each iteration, one of the halves, in this case the right half R, is input to a round function that also takes as input an internal key, K. In FIG. 1, the round function is indicated by f.sub.1, f.sub.2, . . . f.sub.n (in DES, f.sub.1 =f.sub.2 = . . . =f.sub.16).
FIG. 2 illustrates round function, f. Round function f takes two inputs, the right half R of the block and an internal key K (Step 220). Right half R is expanded to 48 bits (Step 222) and XORed with K (Step 224). The result is divided into 8 parts and each 6-bit section is input to one of eight different substitution boxes, or S-boxes (Step 226). An m.times.n S-box is simply a mapping of m input bits to n output bits, and may be implemented in hardware or software. In the DES process, each S-box is a nonlinear substitution, mapping 6 input bits into 4 output bits. The eight outputs of the S-boxes are concatenated (Step 228) and then permuted (Step 230).
Unauthorized persons will attempt to exploit cryptosystems such as DES using mathematical analytic attacks, such as differential and linear cryptanalysis. Differential cryptanalysis looks at pairs of plaintext blocks and their corresponding ciphertext blocks and constructs a table of possible input versus output differences. The resulting table, called an XOR table, may indicate characteristics that can lead to the key in use. Linear cryptanalysis is a cryptanalytic attack that uses linear approximations to compute the key bits. The attack uses S-box approximations and is very successful against S-boxes that have low nonlinearity.
Much of the security of block ciphers based on Feistel networks depends on the properties of the S-boxes used in the round function. Generally, the larger the S-box, the better the security of the block cipher. Although S-boxes may be nonlinear, S-boxes that are not carefully designed to exhibit certain ideal properties may generate a skewed distribution of XOR outputs for given XOR inputs, making them susceptible to differential cryptanalysis. For more information on the relationship between the distribution of output XORs and susceptibility to differential cryptanalysis, see Carlisle M. Adams, "On immunity against Biham and Shamir's Differential Cryptanalysis," Information Processing Letters, vol. 41, Feb. 14, 1992, pp. 77-80.
Many scientists in the field have studied what theoretical operational properties S-boxes should have in order to be relatively resistant to cryptanalytic attack. Some scientists, for example, have proposed that an ideal S-box would have all entries in the XOR table equal to 0 or 2. See E. Biham and A. Shamir, "Differential Cryptanalysis of DES-like Cryptosystems," Advances in Cryptology: Proceedings of CRYPTO '90, Springer-Verlag, Berlin, 1991, pp. 1-21.
Other scientists have proposed that ideal S-boxes satisfy what is called "strict avalanche criterion" (SAC). See A. F. Webster and S. E. Tavares, "On the Design of S-boxes", Advances in Cryptology: Proceedings of CRYPTO '85, Springer-Verlag, New York, 1986, pp. 523-34 S-boxes algorithms that satisfy the strict avalanche criterion produce output bits that change with a probability of one half whenever a single input bit is complemented.
FIG. 3 shows a sample representation to illustrate the size and format of an S-box as known in the art. An m.times.n S-box may be represented as a 2.sup.m .times.n binary matrix, M, where each column is a binary vector which corresponds to a Boolean function of the m input variables, and which defines the response of a single output bit to any given input. Row i of M, 1.ltoreq.i.ltoreq.2.sup.m is therefore the n-bit output vector that results from the ith input vector. An S-box with good avalanche properties would be one in which the sum (modulo 2) of any pair of rows in M would be approximately half zeros and half ones.
Furthermore, scientists have discovered that if bent function-based columns are used for columns of an S-box, the S-box will behave in an "ideal" fashion with respect to avalanche properties. Any change in the m input bits will cause each of the n output bits to change with probability 1/2. A column of M is considered bent if the normalized resultant vector of a two-dimensional Walsh-Hadamard transform of the binary column has all its coefficients either +1 or -1. The Walsh-Hadamard transform is a binary analog of the Fourier transform.
A very large number of known binary vectors may be used to construct the S-box matrix, M. It has been further proposed that if all linear combinations of S-box columns are also bent, the S-box will be more resistant to linear cryptanalytic attacks. See E. Biham, "On Matsui's Linear Cryptanalysis", Advances in Cryptology-Proceedings of EUROCRYPT '94, Springer-Verlag, Berlin, 1995, pp. 341-355.
In general, an ideal S-box would possess the following properties:
I1. All linear combinations of S-box columns are bent;
I2. All entries in the S-box XOR table are 0 or 2;
I3. The S-box satisfies a maximum order strict avalanche criterion;
I4. The S-box satisfies a maximum order bit independence criterion;
I5. The weights of rows has a binomial distribution with mean n/2;
I6. The weights of all pairs of rows has a binomial distribution with mean n/2; and
I7. The columns are each of Hamming weight 2.sup.n-1. (The Hamming weight is the number of 1s in a binary vector).
As mentioned earlier, S-boxes that have property I1 will be more resistant to linear cryptanalysis. S-boxes having property I2 would be protected against differential cryptanalysis. Properties I1, I5, and I7 help to ensure a good static characteristic which means that for any particular input, the output appears to have been randomly generated. Properties I2, I3, I4, and I6 help to ensure a good dynamic characteristic, meaning that as one of the inputs is changed, the change in the resulting output appears random. Not all of these properties, however, can be achieved simultaneously.
Although these properties have been studied extensively, relatively little work has been done to determine to what degree these properties are achievable in practice. Block ciphers that currently need large S-boxes often use random S-boxes rather than constructed S-boxes because the methods of construction of S-boxes traditionally have been computationally slow to implement. Furthermore, many scientists in the field believe that it would be difficult to construct S-boxes using specific mathematical techniques that would result in S-boxes that exhibited random-like properties. For this reason, existing systems typically generate random S-boxes and test them for the desired properties. This method is likewise computationally inefficient (particularly for large S-boxes).
It is therefore desirable to increase the security of existing ciphers that use S-boxes by constructing S-boxes with ideal characteristics rather than using randomly generated S-boxes.
In addition, it is desirable to construct an S-box that is resistant to known cryptanalytic attacks.
It is further desirable to provide a method of constructing an S-box with as many as possible of the "ideal" characteristics mentioned above.
It is still further desirable to reduce the processing time to construct S-boxes with ideal characteristics.
To meet these desires, a method consistent with this invention begins with an S-box smaller than desired but having certain characteristics. That S-box is augmented to form a larger S-box with those same characteristics, and this augmentation repeats until a S-box of the proper size is formed.